package com.soul.sort;

import java.util.Arrays;

/**
 * 堆排序
 */
public class HeapSort {

    public static void sort(int[] a){
        maxHeap(a,a.length);
        for (int i = a.length-1; i >= 0; i--) {
            //每次都与根节点（最大的值）进行交换
            SortUtil.swap(a,0,i);
            //将剩余的数组元素构建为最大堆
            maxHeap(a,i);
        }
    }

    //构建最大堆
    public static void maxHeap(int[] a,int len){
        for (int i = len / 2; i >= 0; i--) {
            buildMax(a,i,len);
        }
    }
    private static void buildMax(int[] a,int rt,int n){
        int l = rt * 2 + 1;
        int r = rt * 2 + 2;
        int max = rt;
        if (l < n && a[l] > a[max]){
            max = l;
        }
        if (r < n && a[r] > a[max]){
            max = r;
        }
        if (max != rt){
            SortUtil.swap(a,rt,max);
            buildMax(a,max,n);
        }
    }

    //构建最小堆
    private static void minHeap(int[] a,int rt,int n){
        if (n == rt){
            return;
        }
        for (int i = n/2; i >= 0; i--) {
            minHeap(a,i,n-1);
            if (a[n-1] < a[(n-1)/2]) {
                SortUtil.swap(a,n-1,(n-1)/2);
            }
        }
    }

    //检查是否是最大堆
    private static boolean checkMax(int[] a,int rt){
        int l = rt * 2 + 1 >= a.length ? -1 : rt * 2 + 1;
        int r = rt * 2 + 2 >= a.length ? -1 : rt * 2 + 2;
        if ((l == -1 || a[rt] > a[l]) && (r == -1 || a[rt] > a[r])){
            boolean c1 = l != -1 ? checkMax(a, l) : true;
            boolean c2 = r != -1 ? checkMax(a, r) : true;
            if (c1 && c2){
                return true;
            }
        }
        return false;
    }

    //检查是否是最小堆
    private static boolean checkMin(int[] a,int rt){
        int l = rt * 2 + 1 >= a.length ? -1 : rt * 2 + 1;
        int r = rt * 2 + 2 >= a.length ? -1 : rt * 2 + 2;
        if ((l == -1 || a[rt] < a[l]) && (r == -1 || a[rt] < a[r])){
            boolean c1 = l != -1 ? checkMin(a, l) : true;
            boolean c2 = r != -1 ? checkMin(a, r) : true;
            if (c1 && c2){
                return true;
            }
        }
        return false;
    }
}
